
import java.util.Arrays;

public class heapsort1 {
    public static void main(String[] arges){
        int[] arr = {15, 65, 23, 19, 8, 72, 35, 4, 10};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] array){ //构建大顶堆
        for (int i=array.length/2-1;i>=0;i--){ //确定好要调整的非叶子节点i，调用adjustHeap方法调整当前堆，然后递减直到根节点0
            adjustHeap(array,i,array.length);
//            System.out.print(i+" "); //查看当前非叶子节点
        }
        for(int j=array.length-1;j>=0;j--){
            swap(array,0,j);// 将大顶堆的根元素放到最后
            System.out.print(array[j]+" "); //查看当前最大元素
            adjustHeap(array,0,j);
        }
    }
    //调整当前堆
    public static void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        int k=i*2+1;
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点
                arr[i] = arr[k];
                i = k;
            }

        arr[i] = temp;//将temp值放到最终的位置
    }
    public static void swap(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}